import java.util.Arrays;




public class Demo1 {
    /*public static void main(String[] args) {
        int[] arr = {1,2,5,4,3};
        for(int i = 0; i < arr.length; i++){
            int tmp = arr[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(arr[j] > tmp){
                    arr[j + 1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = tmp;
        }

        System.out.println(Arrays.toString(arr));
    }*/


    public static void shellSort(int[] arr){
        int gap = arr.length;
        while(gap >1){
            gap = gap / 2;
            shell(arr,gap);
        }
    }

    public static void shell(int[] arr,int gap){
        for(int i = gap; i < arr.length; i++){
            int tmp = arr[i];
            int j = i - gap;
            for(; j >= 0; j-=gap){
                if(arr[j] > tmp){
                    arr[j + gap] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

    public static void heapSort(int[] arr){
        createHeap(arr);
        //数组的长度
        int end = arr.length - 1;
        while(end > 0){
            swap(arr,0,end);
            siftDown(arr,0, end);
            end--;
        }

    }

//创建大根堆
    public static void createHeap(int[] arr){
        //这个循环是起点是从最后一个父节点开始算，每完成一次--，到下一个父节点，直到索引0
        for(int parent = (arr.length - 1 - 1)/2; parent >= 0; parent--){
           siftDown(arr,parent,arr.length);
        }
    }

    public static void siftDown(int[] arr,int parent,int len){
        //找到最后父节点的子节点的索引
        int child = (parent * 2) + 1;
        //确保child是小于数组长度，然后循环进行交换
        while(child < len){
            //防止没有右节点，所以要添加child+1 < len的条件
            if(arr[child] < arr[child + 1] && child+1 < len){
                //到右节点，证明右节点比左节点大
                child++;
            }
            //说明子节点比父节点要大，所以进行交换
            if(arr[child] > arr[parent]){
                swap(arr,parent,child);
                //交换后child的索引在原来父节点的位置，为了让父节点到上一个父节点，让parent = child
                parent = child;
                child = (parent * 2) + 1;
            }else{
                break;
            }
        }
    }
    //用于交换



    public static void selectSort(int[] arr){
        for(int i = 0; i < arr.length; i++){
            int minindex = i;
            for(int j = i + 1; j < arr.length; j++){
                if(arr[j] < arr[minindex]){
                    minindex = j;
                }
                swap1(arr,i,minindex);
            }
        }
    }
    public static void swap1(int[] arr,int parent,int child){
        int tmp = arr[child];
        arr[child] = arr[parent];
        arr[parent]  =tmp;
    }

    public static void bubleSort(int[] arr){
        for(int i = 0; i < arr.length; i++){
            //用于判断是否进入了循环
            boolean flg = false;
            for(int j = 0; j < arr.length - i - 1; j++){
                if(arr[j] > arr[j + 1]){
                    swap2(arr,j,j+1);
                    //说明进入了循环，还没排序完
                    flg = true;
                }
            }
            //说明flg == false，没有循环，排序完成
            if(!flg){
                return;
            }
        }
    }
    public static void swap2(int[] arr,int parent,int child){
        int tmp = arr[child];
        arr[child] = arr[parent];
        arr[parent]  =tmp;
    }

   /* public static void quickSort(int[] arr,int start,int end){
        quick(arr,0, arr.length);
    }
    public static void quick(int[] arr,int start,int end){
        //用于推出递归，达到这个条件说明数组为空或者已经有序了
        if(start >= end){
            return;
        }
        int par = pattion(arr,start,end);
        quick(arr,start,par - 1);
        quick(arr,par+1,end);

    }*/

   /* public static int pattion(int[] arr,int low,int high){
        int tmp = arr[low];
        //记录原来low的下标
        int i = low;
        while (high > low){
            while(arr[high] >= tmp && high > low){
                high--;
            }
            while(arr[low] <= tmp && high > low){
                low++;
            }
            //用于low和high未相遇时交换
            swap(arr,low,high);
        }
        //用于最后一步tmp值和low下标的值交换
        swap(arr,i,low);
        //返回的值时par

        return low ;
    }*/








   /* public static int pattion(int[] arr,int low,int high){
        //新坑位
        int tmp = arr[low];
        while(high > low){
            while(high > low && arr[high] > tmp){
                high--;
            }
            //从后面开始，找到合适的元素，将他直接存入新坑位
            arr[low] = arr[high];
            while(high > low && arr[low] < tmp){
                low--;
            }
            //从前面开始找到合适的元素，将他直接存入新坑位
            arr[high]  =arr[low];
        }
       //当 low == high时，将tmp的值放入low下标这，作为基准值
        arr[low] = tmp;
        return low;
    }*/

    public static void quickSort(int[] arr,int start,int end){
        quick(arr,0, arr.length);
    }
    public static void quick(int[] arr,int start,int end){
        //用于推出递归，达到这个条件说明数组为空或者已经有序了
        if(start >= end){
            return;
        }
        //获得三数中间值
        int index = threeMid(arr,start,end);
        //用于交换中间值
        swap(arr,start,index);
        int par = pattion(arr,start,end);
        quick(arr,start,par - 1);
        quick(arr,par+1,end);

    }
    private static int threeMid(int[] arr,int low,int high){
        //获取中间值
        int mid = (low + high) / 2;
        //查看谁是中间数
        if(arr[low] < arr[high]){
            if(arr[mid] < arr[low]){
                return low;
            }else if(arr[mid] > arr[high]){
                return high;
            }else {
                return mid;
            }
        }else{
            if(arr[mid] < arr[high]){
                return high;
            }else if(arr[mid] > arr[low]){
                return low;
            }else{
                return mid;
            }
        }
    }
    public static int pattion(int[] arr,int left,int right){
        int cur = left + 1;
        int pre = left;
        while(cur <= right){
            if(arr[cur] < arr[left] && arr[++pre] != arr[cur]){
                swap(arr,cur,pre);
            }
            cur++;
        }
        swap(arr,pre,left);
        return pre;
    }
    public static void swap(int[] arr,int parent,int child){
        int tmp = arr[child];
        arr[child] = arr[parent];
        arr[parent]  =tmp;
    }



    public static void mergeSort(int[] arr){
        mergeSortChild(arr,0,arr.length);
    }
    public static void mergeSortChild(int[] arr,int left,int right){
        if(left >= right){
            return;
        }
        int mid = (right + left) / 2;
        mergeSortChild(arr,left,mid);
        mergeSortChild(arr,mid+ 1,right);
        //合并
        merge(arr,left,mid,right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] tmp = new int[right - left -1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //这个是用来确定s1是否超过e1
        while(s1 <= e1 && s2 <= e2){
            if(arr[s1] <= arr[s2]){
                tmp[k] = arr[s1];
                k++;
                s1++;
            }else{
                tmp[k] = arr[s2];
                k++;
                s2++;
            }
        }
        while(s1 <= e1){
            tmp[k] = arr[s1];
            k++;
            s1++;
        }
        while(s2 <= e2){
            tmp[k] = arr[s2];
            k++;
            s1++;
        }
        for(int i = 0; i < arr.length; i++){
            arr[i] = tmp[i];
        }
    }
}












